[UVa] 10271 - Chopsticks

前言

要講這題之前先看一下基本題，今天有N雙筷子，每一個人拿兩雙，請算出每個人所拿筷子差的平方和最小值為多少。

先將筷子從小到大排序，可以知道說對於每一雙筷子來說，與它差最小的一定是和這雙筷子相鄰的那雙。

因此假設dp(i,j)代表i個人，到第j雙筷子的最小值，可以得到

dp(i,j) = min(dp(i,j-1),dp(i-1,j-2) + (l[j] - l[j-1])^2 )

接下來看這一題。

題意

每個人必須拿三雙筷子，但只計算較小的兩雙差的平方和，最長不計，另外不論客人多少人都要加上8個人。

解法

原本是由小排到大，所以第j雙一定是到目前為止最大的那一雙，但如此一來就不能保證還有更大的一雙可以拿，所以換個方式改成由大排到小。

因此得到下式

dp(i,j) = min(dp(i,j-1),dp(i-1,j-2) + (l[j] - l[j-1])^2 ) if j >= i * 3

程式

#include <iostream>
#define MAXNUM 999999999
using namespace std;

int dp[1001][5001] ;
int chopsticks[5001] ;

int main() {
	int number , K , N ;
	for ( int i = 0 ; i < 1001 ; i ++ )
		dp[i][0] = MAXNUM ;
	for ( int i = 0 ; i < 5001 ; i ++ )
		dp[0][i] = 0 ;
	cin >> number ;
	for ( int n = 0 ; n < number ; n ++ ){
		cin >> K >> N ;
		K += 8 ;
		for ( int i = N  ; i > 0 ; i -- ){
			cin >> chopsticks[i] ;
		}
		for ( int i = 1 ; i < K + 1 ; i ++ ){
			for ( int j = 1 ; j < N + 1 ; j ++ ){
				if ( j < i * 3 ){
					dp[i][j] = MAXNUM ;
				} else if ( j >= i * 3 ){
					dp[i][j] = min(dp[i][j-1],dp[i-1][j-2]+(chopsticks[j]-chopsticks[j-1])*(chopsticks[j]-chopsticks[j-1])) ;
				}
			}
		}
		cout << dp[K][N] << endl ;
	}
	return 0;
}